package com.xyj.week02;

import java.util.Arrays;

/**
 * 大根堆
 */
public class T3 {

    public static void main(String[] args) {
        T3 t3 = new T3(8);
        System.out.println("初始化堆为："+ Arrays.toString(t3.nums)+"有效长度为"+t3.heapSize);
        t3.push(1);
        t3.push(3);
        t3.push(4);
        t3.push(5);
        t3.push(6);
        t3.push(7);
        t3.push(8);
        System.out.println("插入7后堆为："+ Arrays.toString(t3.nums)+"有效长度为"+t3.heapSize);
        System.out.println("堆中最大值为"+t3.deleteTheBigOne());
        System.out.println("删除最大元素后堆为："+ Arrays.toString(t3.nums)+"有效长度为"+t3.heapSize);

    }
    /**
     * 有效堆的大小
     */
    public int heapSize;

    /**
     * 数组最大值
     */
    public Integer limit;

    /**
     * 数组
     */
    public int[] nums;

    public T3(Integer limit){
        this.limit=limit;
        this.nums=new int[limit];
    }


    /**
     * 返回大根堆的最大元素，并且维护这个大根堆
     */
    public Integer deleteTheBigOne(){
        //先记录一下第一个元素，
        int bigOne = nums[0];
        //交换最后一个元素和第一个元素，然后堆的容量减1
        swap(nums,0,--heapSize);
        //维护堆的序列从顶往下找，
        // 如果子节点的值更小，就交换，从第一个位置找到最后
        maintain(nums,0,heapSize);
        return bigOne;
    }


    private void maintain(int[] nums, int index, int heapSize) {
        int left =2*index+1;
        while (left<heapSize){
            //如果子节点的索引还在堆的范围内，就继续往下找
            int max= left+1<heapSize&&nums[left]<nums[left+1] ? left+1 :left;
            if (nums[max]>nums[index]){
               //如果子节点更大，就交换
               swap(nums, index, max);
            }
            index=max;
            left=2*index+1;
        }
    }

    /**
     * 添加一个元素
     * @param data 元素
     */
    public void push(Integer data){
        if (heapSize==limit){
            throw new RuntimeException("heapSize weak ！！");
        }
        nums[heapSize]=data;
        this.heapInsert(nums,heapSize++);
    }

    private void heapInsert(int[] nums, Integer index) {
        while(nums[(index-1)/2]<nums[index]){
            swap(nums,(index-1)/2,index);
            index=(index-1)/2;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp= nums[i];
        nums[i]= nums[j];
        nums[j]=temp;
    }
}
